package foundation.graph;

import java.util.Arrays;
import java.util.Stack;

public class courseSchedule {
    public static int MAXN = 20001;
    public static int[] head = new int[MAXN];
    public static int[] next = new int[MAXN];
    public static int[] to = new int[MAXN];
    private static int[] in = new int[MAXN];
    public static int cur;
    private static int n;


    public int[] findOrder(int numCourses, int[][] prerequisites) {
        cur = 1;
        n = 0;
        Arrays.fill(head, 0, numCourses, 0);
        Arrays.fill(in, 0, numCourses, 0);


        for (int[] ints : prerequisites) {
            addEdge(ints[0], ints[1]);
        }
        return dfs(numCourses);
    }

    private void addEdge(int x, int y) {
        next[cur] = head[x];
        to[cur] = y;
        head[x] = cur++;
        in[y]++;
    }

    private int[] dfs(int numCourses) {
        int[] ans = new int[numCourses];
        Stack<Integer> stack = new Stack<>();
        int completedCourses = 0;

        // 将入度为0的课程入栈
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                stack.push(i);
                in[i]--; // 防止重复处理该节点
            }
        }

        while (!stack.isEmpty()) {
            int x = stack.pop();
            ans[completedCourses++] = x;
            for (int ei = head[x]; ei > 0; ei = next[ei]) {
                int y = to[ei];
                in[y]--;
                if (in[y] == 0) {
                    stack.push(y);
                    in[y]--; // 防止重复处理该节点
                }
            }
        }

        if (completedCourses == numCourses) {
            return ans;
        } else {
            return new int[]{};
        }
    }
}


